Oblivious RAM

24 July 2024 (updated 24 July 2024)

Assume we can execute a program in a trusted environment (TEE), but we have only a limited amount of memory locally. We do have access to a lot of external memory, but this is not trusted.

As a first step, we can generate a private key in the TEE and use authenticating encryption to make it so only the TEE can read and write external memory (in this context referred to as RAM). Encrypting the

To make this efficient we encrypt individual pages of e.g. $4\ \mathrm{kB}$. This allows us to efficiently read and write individual pages of memory,

https://en.wikipedia.org/wiki/Oblivious_RAM

Linear scan

Simple ORAM

CP13 present a simple scheme

Ring ORAM

https://eprint.iacr.org/2014/997

Circuit ORAM

Path ORAM

https://crates.io/crates/mc-oblivious-ram

https://www.youtube.com/watch?v=jGr7Nj3KJ3c

https://github.com/odslib/EnigMap/tree/main/ods/oram